/**
* @param {number} poured
* @param {number} query_row
* @param {number} query_glass
* @return {number}
*/
// 错误解法！！
var champagneTower = function (poured, query_row, query_glass) {
    if (query_row == 0) {
        if (poured >= 1) {
            return 1
        } else {
            return poured
        }
    }

    if (poured < (query_row * (query_row + 1) / 2)) {
        return 0
    } else if (poured >= ((query_row + 1) * (query_row + 2) / 2)) {
        return 1
    } else {
        let curr = poured - (query_row * (query_row + 1) / 2)
        let perChanmpagne = curr / (query_row * 2)
        if (query_glass == 0 || query_glass == query_row) {
            return perChanmpagne
        } else {
            return perChanmpagne * 2
        }
    }
};

// 动态规划
var champagneTower = function (poured, query_row, query_glass) {
    // dp[i][j] 为第 i 行第 j 列杯子所经过的水量（而不是最终剩余的水量）
    let dp = Array(query_row + 10).fill(0).map(() => {
        return new Array(query_row + 10).fill(0)
    })
    dp[0][0] = poured

    for (let i = 0; i <= query_row; i++) {
        for (let j = 0; j <= i; j++) {
            if (dp[i][j] <= 1) continue
            dp[i + 1][j] += (dp[i][j] - 1) / 2
            dp[i + 1][j + 1] += (dp[i][j] - 1) / 2
        }
    }

    // 比较流量和1的大小取小者
    return Math.min(dp[query_row][query_glass], 1)
};